package com.nolon.flange.tools


class CuttingPlanner(
    private val lengths: IntArray,
    private val counts: IntArray,
    private val rawLength: Int,
    private val maxCombination: Int = 5,
) {
    private val prodList: IntArray
    private val numList: IntArray
    private val types: Int
    public var finalIntArrayLength = 0

    init { // 在构造函数中运行一次
        //对lengths和counts进行处理，合并可能存在的lengths,不排序
        val tempLengths = IntArray(lengths.size) // lengths.size 应该等于counts.size!
        val tempCounts = IntArray(lengths.size)
        var cursor = 0
        for (i in lengths.indices) {
            val curLen = lengths[i]
            var unique = true
            for (j in tempLengths.indices) {
                if (tempLengths[j] == curLen) {
                    tempCounts[j] += counts[i]
                    unique = false
                }
            }
            if (unique) {
                tempLengths[cursor] = curLen
                tempCounts[cursor] = counts[i]
                cursor++
            }
        }
        types = cursor  //处理完毕以后cursor指在第一个0或者末端
        prodList = IntArray(cursor)
        numList = IntArray(cursor)
        System.arraycopy(tempLengths, 0, prodList, 0, cursor)
        System.arraycopy(tempCounts, 0, numList, 0, cursor)
    }

    /**
     * 输出方案的结构
     * 【x1,x2,x3,x4...xn,count,combination,remainder,repeatable】
     * count = x1+x2+...xn
     * combination = x1,x2...xn中不为零的个数
     * remainder 剩余
     * repeatable 持续切的次数
     */
    // 定义一些方案中的位置信息
    private val planLength = lengths.size + 2
    private val first = 0
    private val last = types - 1
    private val remainderPos = types
    private val repeatPos = types + 1


    /**
     * 这个类是个生成Plan的中间过程类，应该被优化掉……
     *
     * [hitTime] 表示这个类的对象被访问的次数
     * [tempIds] 存放零件的id，[-1,0,0,1,1,1,3,3] 则表示有1个-1（-1代表firstId,这个对象不需要知道是谁）
     *                          2个id为0的零件
     *                          3个id为1的零件
     *                          2个id为3的零件
     *           这种结构方式和plan是不一样的！！！
     *
     */
    inner class SumDetail {
        var hitTime = 0
        var tempIds: IntArray = IntArray(1) { -1 }
        var planScore = 0
    }


    // 临时变量，只在solve中试用一次，删掉
    var plans: List<IntArray> = listOf()

    /**
     * 先放prodList,再放解决方案
     */
    fun solve(repeat: Int): IntArray {
        val bestPlan = generateSolution(repeat)
        val len = (bestPlan.size + 1) * planLength
        finalIntArrayLength = len
        val ret = IntArray(len)
        System.arraycopy(prodList, 0, ret, 0, types)
        for (i in 1..bestPlan.size) {
            System.arraycopy(bestPlan[i - 1], 0, ret, planLength * i, planLength)
        }
        plans = bestPlan  //测试用的，最后删掉
        return ret
    }


    private fun generateSolution(
        repeat: Int,
    ): List<IntArray> {
        var bestPlan: List<IntArray> = listOf()

        var notImprovedCount = 0      // 随着执行次数增多，这个变量会增加，从而触发元素乱序函数
        var bestRawCount = Int.MAX_VALUE // 最好的方案使用的原材料数
        var bestTail = rawLength         // 最好的方案中的最长余料
        var prodScore = IntArray(types)  // 给零件评分，初始都为0，运行到一定次数才赋值
        var prodSeq = (first..last).toList().toIntArray() //初始[0,1,2,...,n]

        for (run in 1..repeat) {

            val prodReq = numList.clone()

            var rawCount = 0
            var maxRemainder = 0
            var patterns = 0

            val cutPlans = arrayListOf<IntArray>()

            while (isReqLeft(prodReq)) {

                val relaxH = if (rawLength / 20 > 300) {
                    300
                } else rawLength / 20

                val relaxRange = (13 * run).rem(relaxH)

                val plan = genAPlan(
                    prodSeq,
                    prodList,
                    prodReq,
                    prodScore,
                    rawLength,
                    maxCombination,
                    relaxRange
                )

                for (i in first..last) {
                    prodReq[i] -= plan[repeatPos] * plan[i]
                }

                cutPlans.add(plan)

                if (plan[remainderPos] > maxRemainder) {
                    maxRemainder = plan[remainderPos]
                }


                rawCount += rawLength * plan[repeatPos]
                patterns++
            }

            notImprovedCount++

            if (bestRawCount > rawCount) {
                bestRawCount = rawCount
                bestTail = maxRemainder
                bestPlan = cutPlans
            } else if (bestRawCount == rawCount) {
                if (bestTail < maxRemainder || bestPlan.size > patterns) {
                    bestTail = maxRemainder
                    bestPlan = cutPlans
                }
            }
            if (notImprovedCount >= 10) {
                prodSeq = genRandSeq(prodSeq)
                prodScore = genRandScore(prodScore, rawLength)
            } else {
                prodSeq = adjustProdSeq(bestPlan, prodSeq)
            }
        }
        return bestPlan
    }

    /**
     * 对[prodSeq] 打乱顺序
     */
    private fun genRandSeq(prodSeq: IntArray): IntArray {
        val newSeq = prodSeq.toList().shuffled()
        for (i in first..last) {
            prodSeq[i] = newSeq[i]
        }
        return prodSeq
        // 下面是旧的实现方法
//        var p1 = 0
//        var p2 = 0
//        var swap = 0
//        for (i in prodSeq.indices) {
//            p1 = (0 until types).random()
//            p2 = (0 until types).random()
//            swap = prodSeq[p1]
//            prodSeq[p1] = prodSeq[p2]
//            prodSeq[p2] = swap
//        }
    }

    private fun adjustProdSeq(
        bestPlan: List<IntArray>,
        prodSeq: IntArray
    ): IntArray {
        for (i in bestPlan.indices) {
            val repeat = bestPlan[i][repeatPos]
            val rawRemain = bestPlan[i][remainderPos] // 原本用做判断条件，现在不用了
            if (repeat <= 1) { // && rawRemain >= relaxRange
                for (id in prodList.indices) {
                    if (bestPlan[i][id] > 0) {
                        liftProdSeq(prodSeq, id)
                    }
                }
            }
        }
        return prodSeq
    }

    /**
     * 把指定的[idToLift]移动到Sequence前面
     */
    private fun liftProdSeq(prodSeq: IntArray, idToLift: Int) {
        for (i in prodSeq.indices) {
            if (prodSeq[i] == idToLift) {
                val p2 = i
                var p1 = p2 - 10
                if (p1 <= 0) {
                    p1 = 0
                }
                for (k in p2 - 1 downTo p1) {
                    prodSeq[k + 1] = prodSeq[k]
                }
                prodSeq[p1] = idToLift
                break
            }
        }
    }


    /**
     * 对不同长度的零件随机一个分数，零件越长，分数可能越大
     * r = 原料长度
     * 如果Li>r/2, 在[0,80]之间随机取整数分
     * 如果Li>r/3,但是小于r/2,在【0，40】之间随机取分
     */
    private fun genRandScore(prodScore: IntArray, targetLen: Int): IntArray {
        // 新实现
        val t2 = targetLen / 2
        val t3 = targetLen / 3
        val t4 = targetLen / 4
        val t5 = targetLen / 5
        for (i in prodScore.indices) {
            prodScore[i] = when (prodList[i]) {
                in t2..Int.MAX_VALUE -> (0..80).random()
                in t3 until t2 -> (0..40).random()
                in t4 until t3 -> (0..30).random()
                in t5 until t4 -> (0..20).random()
                else -> 0
            }
        }
        return prodScore
    }

    /**
     * 判断给定的numList是不是全部都是0
     */
    private fun isReqLeft(numList: IntArray): Boolean {
        return numList.any { it > 0 }
    }

    private fun genAPlan(
        prodSeq: IntArray,
        prodLen: IntArray,
        prodReq: IntArray,
        prodScore: IntArray,
        rawLen: Int,
        maxComb: Int,
        relaxRange: Int,
    ): IntArray {

        var lenList = intArrayOf() //存放可能的其他长度，
        var idList = intArrayOf()  //存放长度的id

        var firstId = -1
        var firstLen = 0

        // 取一个需求数量大于0的放在前面
        for (i in first..last) {
            val id = prodSeq[i]
            val req = prodReq[id]
            val len = prodLen[id]
            if (req > 0 && len <= rawLen) {
                firstId = id
                firstLen = len
                break
            }
        }

        val plan = IntArray(planLength)
        plan[remainderPos] = rawLen - firstLen
        plan[firstId] += 1

        // 尽量放这种
        for (i in first..last) {
            val id = prodSeq[i]
            val len = prodLen[id]
            val req = prodReq[id]

            if (req > 0 && len <= rawLen) {
                // 全部放这个能放多少个
                var maxNum = rawLen / len
                if (maxNum > req) maxNum = req
                if (id == firstId) maxNum--
                for (j in 1..maxNum) {
                    // intArrayOf(vararg) 接收多个Int元素组成数组，*lenList可以把lenList展开放在这里
                    lenList = intArrayOf(*lenList, len)
                    idList = intArrayOf(*idList, id)
                }
            }
        }

        if (lenList.isNotEmpty()) {
            val chosen =
                solveSubsetSum(lenList, idList, prodReq, prodScore, firstId, rawLen - firstLen, relaxRange)
            if (chosen.isNotEmpty()) {
                // 跳过第一个
                for (i in 1..chosen.lastIndex) {
                    val id = chosen[i]
                    plan[id] += 1
                    plan[remainderPos] -= prodLen[id]
                }
            }
        }

        var maxRepeat = Int.MAX_VALUE
        for (i in first..last) {
            if (plan[i] > 0) {
                val repeat: Int = prodReq[i] / plan[i]
                if (repeat in 1..maxRepeat) { //repeat >= 1 && repeat <= maxRepeat
                    maxRepeat = repeat
                }
            }
        }
        plan[repeatPos] = maxRepeat
        return plan
    }

    /**
     * 在指定了一个切割方案的第一个元素以后，使用此方法确定余下的长度切哪些元素，
     * 方法的实现有点问题，使用了一个和原料长度接近的数组，比方说原料长度是6000，则有可能使用一个长度为5000的数组，
     */
    private fun solveSubsetSum(
        candidateLen: IntArray,
        candidateId: IntArray,
        prodReq: IntArray,
        prodScore: IntArray,
        firstId: Int,
        targetSum: Int,
        relaxRange: Int
    ): IntArray {

        val arr: Array<SumDetail> = Array(targetSum + 1) {
            SumDetail()
        }

        val knownSum: IntArray = IntArray(targetSum + 1)

        var last = 0  // 这个last和全局变量last不一样！！！
        var newLast = 0


        for (i in candidateLen.indices) {
            val sum1 = candidateLen[i]
            val id1 = candidateId[i]

            for (j in 0..last) {
                val sum2 = knownSum[j]
                val mysum = sum1 + sum2

                if (mysum > targetSum) {
                    continue
                }

                with(arr[mysum]) {
                    if (hitTime == 0) {
                        hitTime++
                        val temp = intArrayOf(*arr[sum2].tempIds, id1)
                        tempIds = temp
                        planScore = scorePlan(tempIds, prodReq, prodScore, firstId)
                        newLast += 1
                        knownSum[newLast] = mysum
                    } else if (mysum >= targetSum - relaxRange * 1.2) {
                        hitTime++
                        if (hitTime.rem(7) == 0) {
                            val newIds = intArrayOf(*arr[sum2].tempIds, id1)

                            val score1 = planScore
                            val score2 = scorePlan(newIds, prodReq, prodScore, firstId)
                            if (score2 > score1) {
                                tempIds = newIds
                                planScore = score2
                            }
                        }
                    }
                }

            }
            last = newLast
        }

        var best = 0
        var bestScore = Int.MIN_VALUE

        val range = if (relaxRange >= targetSum) { // vba作者自己增加的一段代码,不清楚作用,一般都是false
            targetSum
        } else relaxRange

        for (i in targetSum downTo targetSum - range) {
            if (arr[i].hitTime <= 0) continue

            val score1 = scorePlan(arr[i].tempIds, prodReq, prodScore, firstId)
            if (score1 > bestScore) {
                bestScore = score1
                best = i
            }
        }
        if (best > 0) {
            return arr[best].tempIds
        } else {
            for (i in targetSum downTo 0) {
                if (arr[i].hitTime > 0) {
                    return arr[i].tempIds
                }
            }
            // 返回空，可能会出错
            return intArrayOf()
        }
    }

    /**
     * 给方案进行评分
     */
    private fun scorePlan(
        arr: IntArray,
        prodReq: IntArray,
        prodScore: IntArray,
        firstId: Int,
    ): Int {
        val plan = IntArray(planLength)
        for (i in arr.indices) {
            val id = arr[i]
            if (id > -1) {
                plan[id] += 1
            }
        }
        if (firstId >= 0) {
            plan[firstId] = plan[firstId] + 1
        }
        // 如果不满足maxComb要求，返回0
        var combination = 0
        for (i in first..last) {
            if (plan[i] != 0) combination++
        }
        if (combination > maxCombination) return 0

        var maxRepeat = Int.MAX_VALUE
        for (i in first..last) {
            if (plan[i] <= 0) continue
            val repeat = prodReq[i] / plan[i]
            if (repeat < maxRepeat) {
                maxRepeat = repeat
            }
        }

        var score = 0
        var usage = 0
        for (i in first..last) {
            if (plan[i] > 0) {
                usage += prodList[i] * plan[i]
                score = usage + prodScore[i]
            }
        }
        score *= maxRepeat
        return score
    }
}